การค้นหาและการเรียงลำดับ: พื้นฐานของข้อมูลจำนวนมาก
การค้นหาและการเรียงลำดับไม่ใช่เพียงแค่บทนำของวิชาอัลกอริธึม แต่ยังเป็นตรรกะพื้นฐานในการประมวลผลข้อมูลในวิทยาศาสตร์คอมพิวเตอร์ คุณค่าของข้อมูลขึ้นอยู่กับประสิทธิภาพในการค้นหาและจัดระเบียบ หน้านี้จะแสดงให้เห็นถึงหลักการพื้นฐานที่สุดของการค้นหาแบบตามลำดับเปิดเผยแก่นแท้ของการประเมินอัลกอริธึม — นั่นคือ ภายใต้รูปแบบข้อมูลที่แตกต่างกัน การค้นหาตำแหน่งเป้าหมายโดยใช้การเปรียบเทียบแบบเส้นตรงทำได้อย่างไร
1. ตรรกะและความเสียหาย
การค้นหาแบบตามลำดับ:เริ่มจากองค์ประกอบแรกในรายการ แล้วตรวจสอบทีละตัวตามลำดับเริ่มต้น จนกว่าจะพบองค์ประกอบเป้าหมาย หรือตรวจสอบครบรายการแล้ว ซึ่งความซับซ้อนทางเวลาคือ $O(n)$។
2. การเปรียบเทียบประสิทธิภาพ: แบบไม่เรียงลำดับ กับ แบบเรียงลำดับ
ในรายการที่ไม่เรียงลำดับที่ (ดูตารางด้านล่าง) ไม่ว่าจะสำเร็จหรือล้มเหลว จำนวนการเปรียบเทียบโดยเฉลี่ยมักจะสัมพันธ์กับ $n$ เป็นแบบเชิงเส้น ในขณะที่ในรายการที่เรียงลำดับสามารถใช้กฎการเรียงลำดับของข้อมูลเพื่อให้เกิดการหยุดทำงานล่วงหน้าได้: เมื่อพบองค์ประกอบที่มีค่ามากกว่าเป้าหมาย จะสามารถสรุปได้ทันทีว่าเป้าหมายไม่มีอยู่ แม้ว่าจะไม่เปลี่ยนแปลงลักษณะเดิมของ $O(n)$ แต่ช่วยปรับปรุงประสิทธิภาพโดยเฉลี่ยในการค้นหาที่ล้มเหลว
| ประเภทรายการ | เป้าหมายมีอยู่ (ค่าเฉลี่ย) | เป้าหมายไม่มีอยู่ (ค่าเฉลี่ย) |
|---|---|---|
| ไม่เรียงลำดับ (ตาราง 5-1) | $n/2$ | $n$ |
| เรียงลำดับ (ตาราง 5-2) | $n/2$ | $n/2$ (ปรับปรุง) |